package org.example.everyday;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * <p>
 *
 * @author anlu
 * @date 2022/5/11 0011 8:19
 */
public class Lc449 {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

    public static void main(String[] args) {
        Lc449 lc449 = new Lc449();

        String root = "2,1,3";
        TreeNode treeNode = lc449.deserialize(root);
        String res = lc449.serialize(treeNode);
        System.out.println(res);

    }

    /**
     * 反序列化的方法
     * @param data
     * @return
     */
    private TreeNode deserialize(String data) {
        if(data.isEmpty()){
            return null;
        }
        String[] arr = data.split(",");
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            stack.push(Integer.parseInt(arr[i]));
        }
        return construct(Integer.MIN_VALUE,Integer.MAX_VALUE,stack);
    }

    private TreeNode construct(int minValue, int maxValue, Deque<Integer> stack) {

        if(stack.isEmpty() || stack.peek() < minValue || stack.peek() > maxValue){
            return null;
        }
        //取出栈顶的第一个元素值
        int val = stack.pop();
        TreeNode root = new TreeNode(val);
        root.right = construct(val,maxValue,stack);
        root.left = construct(minValue,val,stack);
        return root;
    }

    /**
     * 方法描述: 序列化的方法
     *
     * @param treeNode .
     * @return java.lang.String
     * @author 安路路
     * @date 2022/5/11 0011  22:12
     */
    private String serialize(TreeNode treeNode) {
        List<Integer> list = new ArrayList<Integer>();

        postOrder(treeNode,list);
        String s = list.toString();
        return s.substring(1,s.length() - 1);
    }
    /**
     * 方法描述: 后续遍历的方法
     *
     * @param root .
     * @param list .
     * @author 安路路
     * @date 2022/5/11 0011  22:14
     */
    private void postOrder(TreeNode root, List<Integer> list) {
        if(root == null){
            return;
        }
        postOrder(root.left,list);
        postOrder(root.right,list);
        list.add(root.val);

    }


}
